package beauty.test.math;

/**
 * 功能描述：算法——欧几里得算法
 *
 * @author RenShiWei
 * Date: 2020/4/9 15:13
 **/
public class 欧几里得算法 {

    /**
     * 功能描述：欧几里得算法——即辗转相除法
     *  求两个数的最大公约数
     * @param
     * @return
     * @author RenShiWei
     * Date: 2020/4/9 15:13
     */
    static int gcd ( int m, int n ) {
        return n == 0 ? m : gcd(n, m % n);
    }

    /*
        欧几里得算法扩展——裴蜀等式

        ➢对任何整数a、b和它们的最大公约数d ,关于未知数x和y的线性丢
            番图方程(称为裴蜀等式) :
            ax + by点m有整数解时当且仅当m是d的倍数。
            裴蜀等式有解时必然有无穷多个整数解,每组解x、y都称为裴蜀数
            可用扩展欧几里得算法(Extended Euclidean algorithm)求得。
        ➢方程12x+42y=6有解
        ➢特别地,方程ax+by=1有整数解当且仅当整数a和b互素

        ==============================================

        ➢扩展欧几里得算法就是在求a,b的最大公约数d=gcd(a,b)的同
            时,求出贝祖等式ax + by = m的一个解(x0,y0)
            ➢如何递推?
                x=y1
                y=x1- a/b*y1
            ➢通解:
                x= x0+ (b/gcd)*t
            所有的x对b同模
                y=y0- (a/gcd)*t
            所有的y对a同模
            ➢如果想要得到x大于0的第一个解?
                b/=d;x = (x0号b+b) 8b
            ➢蓝桥杯2016决赛:-步之遥

            ===========================================
            #扩展欧几里得
            gcd(a,b)
            return b = =0?a
            我们观察到:欧几里德算法停止的状态是: a= gcd，b = 0，那么，这是否能给我们求解x y提供- -种思路呢?
            a'x + b'y = gcd 此时x= =1,y为任意数
            因为，这时候，只要a=gcd的系数是1，那么只要b的系数是0或者其他值
            (无所谓是多少，反正任何数乘以0都等于0但是a的系数- -定要是1)，这时，我们就会有: a*1 + b*0 = gcd
                当然这是最终状态，但是我们是否可以从最终状态反推到最初的状态呢?

                假设当前我们要处理的是求出a和b的最大公约数，并求出x和y使得*x + b*y gcd，--->要求的
                而我们已经求出了下一个状态: b和a%bT的最大公约数，并且求出了- -组x1和y1使得: b*x1 + (a%b)*y1 = gcd  （2），-->下- 一个状态.
                那么这两个相邻的状态之间是否存在一种关系呢?

                a%b = k ==> a = b*(a/b) +k "/"舍掉余数的除法 ==> k=a-(a/b)*b
                我们知道: a%b = a - (a/b)*b (这里的“/”指的是整除，例如5/2=2，1/3=0) ，那么，我们可以进一步得到:
                    gcd = b*x1 + (a-(a/b)*b)*y1
                    = b*x1 + a*y1 - (a/b)*b*y1
                    = a*y1 + b*(x1 - a/b*y1) (3)

                对比之前我们的状态,式(3)和式(1):求一组x和y使得: a*x + b*y = gcd，是否发现了什么?
                这里:
                    x=y1
                    y = x1- a/b*y1
                    这就是递推式，注意x,y是递归过程中的上一-层 ,x1,y1是下一-层得到的值

     */

    static long x,y;





}

